﻿#define _CRT_SECURE_NO_WARNINGS

/*你有一个背包，最多能容纳的体积是V。

现在有n个物品，第i个物品的体积为

（1）求这个背包至多能装多大价值的物品？
（2）若背包恰好装满，求至多能装多大价值的物品？
输入描述：
第一行两个整数n和V，表示物品个数和背包体积。
接下来n行，每行两个数
​
 ，表示第i个物品的体积和价值。*/

/*给你一个 只包含正整数 的 非空 数组 nums 。
请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。*/

#include <iostream>
#include <vector>
using namespace std;

int main() {


    int a, b, n, V;
    cin >> n >> V;
    vector<int> v, w;
    while (cin >> a >> b) { // 注意 while 处理多个 case
        v.push_back(a);
        w.push_back(b);
    }

    vector<vector<int>> dp1(n + 1, vector<int>(V + 1, 0));
    vector<vector<int>> dp2(n + 1, vector<int>(V + 1, 0));
    for (int j = 1; j <= V; j++)
    {
        dp2[0][j] = -1;
    }

    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= V; j++)
        {
            dp1[i][j] = dp1[i - 1][j];
            dp2[i][j] = dp2[i - 1][j];
            if (j - v[i - 1] >= 0)
            {
                dp1[i][j] = max(dp1[i][j], dp1[i - 1][j - v[i - 1]] + w[i - 1]);
                if (dp2[i - 1][j - v[i - 1]] != -1)
                {
                    dp2[i][j] = max(dp2[i][j], dp2[i - 1][j - v[i - 1]] + w[i - 1]);
                }
            }
        }
    }

    cout << dp1[n][V] << endl;
    if (dp2[n][V] != -1)
    {
        cout << dp2[n][V];
    }
    else {
        cout << 0;
    }

    return 0;

}
// 64 位输出请用 printf("%lld")

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int n = nums.size();

        int sum = 0;
        for (auto& it : nums)
        {
            sum += it;
        }
        int num = sum / 2;
        if (sum - num != num)  return false;
        vector<vector<bool>> dp(n + 1, vector<bool>(num + 1, false));

        dp[0][0] = true;
        for (int i = 1; i <= n; i++)
            dp[i][0] = true;
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= num; j++)
            {
                dp[i][j] = dp[i - 1][j] || (j - nums[i - 1] >= 0 && dp[i - 1][j - nums[i - 1]]);
            }
        }

        return dp[n][num];
    }
};


/*给你一个非负整数数组 nums 和一个整数 target 。

向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：

例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。
返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。*/

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int n = nums.size();

        long long sum = 0;
        for (auto& it : nums)
        {
            sum += it;
        }
        long long num = (sum + target) / 2;
        if (num < 0 || (sum + target) % 2) return 0;
        vector<vector<int>> dp(n + 1, vector<int>(num + 1, 0));
        dp[0][0] = 1;

        for (int i = 1; i <= n; i++)
        {
            for (int j = 0; j <= num; j++)
            {
                dp[i][j] = dp[i - 1][j];
                if (j - nums[i - 1] >= 0)  dp[i][j] += dp[i - 1][j - nums[i - 1]];
            }
        }

        return dp[n][num];
    }
};

/*有一堆石头，用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。

每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：

如果 x == y，那么两块石头都会被完全粉碎；
如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。
最后，最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下，就返回 0。*/


class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        int n = stones.size();

        int sum = 0;
        for (auto& it : stones)    sum += it;
        int aim = sum / 2;

        vector<vector<int>> dp(n + 1, vector<int>(aim + 1, 0));
        for (int i = 1; i <= n; i++)
        {
            for (int j = 0; j <= aim; j++)
            {
                dp[i][j] = dp[i - 1][j];
                if (j >= stones[i - 1])
                    dp[i][j] = max(dp[i][j], dp[i - 1][j - stones[i - 1]] + stones[i - 1]);
            }
        }

        return sum - 2 * dp[n][aim];
    }
};